// https://www.lintcode.com/problem/leaf-similar-trees/

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root1: the first tree
     * @param root2: the second tree
     * @return: returns whether the leaf sequence is the same
     */
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        // write your code here.
        List<Integer> l1 = new ArrayList<>();
        List<Integer> l2 = new ArrayList<>();
        Stack<TreeNode> t1 = new Stack<>();
        Stack<TreeNode> t2 = new Stack<>();
        t1.push(root1);
        t2.push(root2);
        dfs(l1, t1);
        dfs(l2, t2);
        if (l1.size() == l2.size()) {
          for (int i = 0; i < l1.size(); ++i) {
            if (l1.get(i) != l2.get(i)) {
              return false;
            }
          }
          return true;
        }
        return false;
    }

    protected void dfs(List<Integer> leafs, Stack<TreeNode> tree) {
      while (!tree.empty()) {
        TreeNode node = tree.pop();
        if ((node.left == null) && (node.right == null)) {
          leafs.add(node.val);
        } else {
          if (node.left != null) {
            tree.push(node.left);
          }
          if (node.right != null) {
            tree.push(node.right);
          }
        }
      }
    }
}